

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/Mine.jpg">
  <link rel="icon" href="/img/Mine.jpg">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Chiam">
  <meta name="keywords" content="算法，安全">
  
    <meta name="description" content="『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）数学–数论–容斥定理完全解析（转）对容斥原理的描述容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。 描述容斥原理可以描述如下： 要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所">
<meta property="og:type" content="article">
<meta property="og:title" content="『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）">
<meta property="og:url" content="http://example.com/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E6%95%B0%E5%AD%A6-%E6%95%B0%E8%AE%BA%E3%80%8F%E5%AE%B9%E6%96%A5%E5%AE%9A%E7%90%86%E5%AE%8C%E5%85%A8%E8%A7%A3%E6%9E%90%EF%BC%88%E8%BD%AC%EF%BC%89/index.html">
<meta property="og:site_name" content="Chiam 的个人主页">
<meta property="og:description" content="『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）数学–数论–容斥定理完全解析（转）对容斥原理的描述容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。 描述容斥原理可以描述如下： 要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDUucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDcucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDgucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDkucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTUucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTU1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTU2LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTcucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTgucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTg1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTkucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjVmaXhlZC5wbmc?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjcucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjg1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjkucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzM1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzUucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzcucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzgucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzg1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzkucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDI1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDM1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDUucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDcucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDgucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDkucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTAucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTEucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTIucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTMucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTM1LnBuZw?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTQucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTUucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTYucG5n?x-oss-process=image/format,png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTcucG5n?x-oss-process=image/format,png">
<meta property="article:published_time" content="2023-12-05T16:11:44.869Z">
<meta property="article:modified_time" content="2023-12-05T16:19:39.754Z">
<meta property="article:author" content="Chiam">
<meta property="article:tag" content="算法，安全">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDAucG5n?x-oss-process=image/format,png">
  
  
  
  <title>『算法-ACM竞赛-数学-数论』容斥定理完全解析（转） - Chiam 的个人主页</title>

  <link  rel="stylesheet" href="https://lib.baomitu.com/twitter-bootstrap/4.6.1/css/bootstrap.min.css" />



  <link  rel="stylesheet" href="https://lib.baomitu.com/github-markdown-css/4.0.0/github-markdown.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/hint.css/2.7.0/hint.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.css" />



<!-- 主题依赖的图标库，不要自行修改 -->
<!-- Do not modify the link that theme dependent icons -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_hj8rtnfg7um.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />


  <link id="highlight-css" rel="stylesheet" href="/css/highlight.css" />
  
    <link id="highlight-css-dark" rel="stylesheet" href="/css/highlight-dark.css" />
  



  
<link rel="stylesheet" href="/css/custom.css">



  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    Fluid.ctx = Object.assign({}, Fluid.ctx)
    var CONFIG = {"hostname":"example.com","root":"/","version":"1.9.5-a","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false,"scope":[]},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"left","visible":"hover","icon":"❡"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"code_language":{"enable":true,"default":"TEXT"},"copy_btn":true,"image_caption":{"enable":true},"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"placement":"right","headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":2},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"follow_dnt":true,"baidu":null,"google":{"measurement_id":null},"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml","include_content_in_search":true};

    if (CONFIG.web_analytics.follow_dnt) {
      var dntVal = navigator.doNotTrack || window.doNotTrack || navigator.msDoNotTrack;
      Fluid.ctx.dnt = dntVal && (dntVal.startsWith('1') || dntVal.startsWith('yes') || dntVal.startsWith('on'));
    }
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
  


  
<meta name="generator" content="Hexo 6.3.0"></head>


<body>
  

  <header>
    

<div class="header-inner" style="height: 70vh;">
  <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Chiam&#39;s Blogs</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                
                <span>首页</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                
                <span>归档</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                
                <span>分类</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                
                <span>关于</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                
                <span>友链</span>
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              <i class="iconfont icon-search"></i>
            </a>
          </li>
          
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">
              <i class="iconfont icon-dark" id="color-toggle-icon"></i>
            </a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

  

<div id="banner" class="banner" parallax=true
     style="background: url('/img/default.png') no-repeat center center; background-size: cover;">
  <div class="full-bg-img">
    <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
      <div class="banner-text text-center fade-in-up">
        <div class="h2">
          
            <span id="subtitle" data-typed-text="『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）"></span>
          
        </div>

        
          
  <div class="mt-3">
    
    
      <span class="post-meta">
        <i class="iconfont icon-date-fill" aria-hidden="true"></i>
        <time datetime="2023-12-06 00:11" pubdate>
          2023年12月6日 凌晨
        </time>
      </span>
    
  </div>

  <div class="mt-1">
    
      <span class="post-meta mr-2">
        <i class="iconfont icon-chart"></i>
        
          7.1k 字
        
      </span>
    

    
      <span class="post-meta mr-2">
        <i class="iconfont icon-clock-fill"></i>
        
        
        
          59 分钟
        
      </span>
    

    
    
  </div>


        
      </div>

      
    </div>
  </div>
</div>

</div>

  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="side-col d-none d-lg-block col-lg-2">
      

    </div>

    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div id="board">
          <article class="post-content mx-auto">
            <h1 id="seo-header">『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）</h1>
            
            
              <div class="markdown-body">
                
                <h1 id="『算法-ACM-竞赛-数学-数论』容斥定理完全解析（转）"><a href="#『算法-ACM-竞赛-数学-数论』容斥定理完全解析（转）" class="headerlink" title="『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）"></a>『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）</h1><h1 id="数学–数论–容斥定理完全解析（转）"><a href="#数学–数论–容斥定理完全解析（转）" class="headerlink" title="数学–数论–容斥定理完全解析（转）"></a>数学–数论–容斥定理完全解析（转）</h1><h3 id="对容斥原理的描述"><a href="#对容斥原理的描述" class="headerlink" title="对容斥原理的描述"></a>对容斥原理的描述</h3><p>容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。</p>
<h4 id="描述"><a href="#描述" class="headerlink" title="描述"></a>描述</h4><p>容斥原理可以描述如下：</p>
<p>要计算几个集合并集的大小，我们要先将所有<strong>单个集合</strong>的大小计算出来，然后减去所有<strong>两个集合相交</strong>的部分，再加回所有<strong>三个集合相交</strong>的部分，再减去所有<strong>四个集合相交</strong>的部分，依此类推，一直计算到<strong>所有集合相交</strong>的部分。</p>
<h4 id="关于集合的原理公式"><a href="#关于集合的原理公式" class="headerlink" title="关于集合的原理公式"></a>关于集合的原理公式</h4><p>上述描述的公式形式可以表示如下：</p>
<hr>
<p>** <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>**</p>
<p>它可以写得更简洁一些，我们将 B 作为所有 Ai 的集合，那么容斥原理就变成了：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>这个公式是由 De Moivre (Abraham de Moivre)提出的。</p>
<h4 id="关于维恩图的原理"><a href="#关于维恩图的原理" class="headerlink" title="关于维恩图的原理"></a>关于维恩图的原理</h4><p>用维恩图来表示集合 A、B 和 C：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>那么<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的面积就是集合 A、B、C 各自面积之和减去<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload> , <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDUucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>, <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload> 的面积，再加上<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的面积。</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDgucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>由此，我们也可以解决 n 个集合求并的问题。</p>
<h4 id="关于概率论的原理"><a href="#关于概率论的原理" class="headerlink" title="关于概率论的原理"></a>关于概率论的原理</h4><p>设事件<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMDkucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload> 代表发生某些事件的概率（即发生其中至少一个事件的概率），则：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>这个公式也可以用 B 代表 Ai 的集合：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<h3 id="容斥原理的证明"><a href="#容斥原理的证明" class="headerlink" title="容斥原理的证明"></a>容斥原理的证明</h3><p>我们要证明下面的等式：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>其中 B 代表全部 Ai 的集合</p>
<p>我们需要证明在 Ai 集合中的任意元素，都由右边的算式被正好加上了一次（注意如果是不在 Ai 集合中的元素，是不会出现在右边的算式中的）。</p>
<p>假设有一任意元素在 k 个 Ai 集合中（k&gt;&#x3D;1），我们来验证这个元素正好被加了一次：</p>
<p>当 size(C)&#x3D;1 时，元素 x 被加了 k 次。</p>
<p>当 size(C)&#x3D;2 时，元素 x 被减了 C(2,k)次，因为在 k 个集合中选择 2 个，其中都包含 x。</p>
<p>当 size(C)&#x3D;3 时，元素 x 被加了 C(3,k)次。</p>
<p>……</p>
<p>当 size(C)&#x3D;k 时，元素 x 被加&#x2F;减了 C(k,k)次，符号由 sign(-1)^(k-1)决定。</p>
<p>当 size(C)&gt;k 时，元素 x 不被考虑。</p>
<p>然后我们来计算所有组合数的和。</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>由二项式定理，我们可以将它变成：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTUucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>我们把 x 取为 1，这时<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTU1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>表示 1-T（其中 T 为 x 被加的总次数），所以<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTU2LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，证明完毕。</p>
<h3 id="对于实际问题的应用"><a href="#对于实际问题的应用" class="headerlink" title="对于实际问题的应用"></a>对于实际问题的应用</h3><p>容斥原理的理论需要通过例子才能很好的理解。</p>
<p>首先，我们用三个简单的例子来阐释这个理论。然后会讨论一些复杂问题，试看如何用容斥原理来解决它们。</p>
<p>其中的“寻找路径数”是一个特殊的例子，它反映了容斥问题有时可以在多项式级复杂度内解决，不一定需要指数级。</p>
<h4 id="一个简单的排列问题"><a href="#一个简单的排列问题" class="headerlink" title="一个简单的排列问题"></a>一个简单的排列问题</h4><p>由 0 到 9 的数字组成排列，要求第一个数大于 1，最后一个数小于 8，一共有多少种排列？</p>
<p>我们可以来计算它的逆问题，即第一个元素&lt;&#x3D;1 或者最后一个元素&gt;&#x3D;8 的情况。</p>
<p>我们设第一个元素&lt;&#x3D;1 时有 X 组排列，最后一个元素&gt;&#x3D;8 时有 Y 组排列。那么通过容斥原理来解决就可以写成：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>经过简单的组合运算，我们得到了结果：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>然后被总的排列数 10!减，就是最终的答案了。</p>
<h4 id="（0-1-2）序列问题"><a href="#（0-1-2）序列问题" class="headerlink" title="（0,1,2）序列问题"></a>（0,1,2）序列问题</h4><p>长度为 n 的由数字 0，1，2 组成的序列，要求每个数字至少出现 1 次，这样的序列有多少种？</p>
<p>同样的，我们转向它的逆问题。也就是不出现这些数字的序列 不出现其中某些数字的序列。</p>
<p>我们定义 Ai(i&#x3D;0…2)表示不出现数字 i 的序列数，那么由容斥原理，我们得到该逆问题的结果为：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTgucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>可以发现每个 Ai 的值都为 2^n（因为这些序列中只能包含两种数字）。而所有的两两组合<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTg1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>都为 1（它们只包含 1 种数字）。最后，三个集合的交集为 0。（因为它不包含数字，所以不存在）</p>
<p>要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMTkucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<h4 id="方程整数解问题"><a href="#方程整数解问题" class="headerlink" title="方程整数解问题"></a>方程整数解问题</h4><p>给出一个方程：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>其中<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>。</p>
<p>求这个方程的整数解有多少组。</p>
<p>我们先不去理会 xi&lt;&#x3D;8 的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把 20 个元素分成 6 组，也就是添加 5 块“夹板”，然后在 25 个位置中找 5 块“夹板”的位置。</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>然后通过容斥原理来讨论它的逆问题，也就是 x&gt;&#x3D;9 时的解。</p>
<p>我们定义 Ak 为 xk&gt;&#x3D;9 并且其他 xi&gt;&#x3D;0 时的集合，同样我们用上面的添加“夹板”法来计算 Ak 的大小，因为有 9 个位置已经被 xk 所利用了，所以：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>然后计算两个这样的集合 Ak、Ap 的交集：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>因为所有 x 的和不能超过 20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为 0。最后我们用总数剪掉用容斥原理所求逆问题的答案，就得到了最终结果：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjVmaXhlZC5wbmc?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<h4 id="求指定区间内与-n-互素的数的个数："><a href="#求指定区间内与-n-互素的数的个数：" class="headerlink" title="求指定区间内与 n 互素的数的个数："></a>求指定区间内与 n 互素的数的个数：</h4><p>给出整数 n 和 r。求区间[1;r]中与 n 互素的数的个数。</p>
<p>去解决它的逆问题，求不与 n 互素的数的个数。</p>
<p>考虑 n 的所有素因子 pi(i&#x3D;1…k)</p>
<p>在[1;r]中有多少数能被 pi 整除呢？它就是：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要运用容斥原理来解决。</p>
<p>我们可以用 2^k 的<a target="_blank" rel="noopener" href="http://lib.csdn.net/base/datastructure">算法</a>求出所有的 pi 组合，然后计算每种组合的 pi 乘积，通过容斥原理来对结果进行加减处理。</p>
<p>关于此问题的最终实现：</p>
<pre><code class="hljs"> 


int solve(int n, int r)
&#123;

    vector&lt;int&gt; p;
    for (int i = 2; i * i &lt;= n; ++i)
        if (n % i == 0)
        &#123;
            p.push_back(i);
            while (n % i == 0)
                n /= i;
        &#125;
    if (n &gt; 1)  p.push_back(n);

    int sum = 0;

    for (int msk = 1; msk &lt; (1 &lt;&lt; p.size()); ++msk)
    &#123;
        int mult = 1,

            bits = 0;

        for (int i = 0; i &lt; (int)p.size(); ++i)
            if (msk &amp; (1 &lt;&lt; i))&#123;
                ++bits;
                mult *= p[i];
            &#125;

        int cur = r / mult;

        if (bits % 2 == 1)
            sum += cur;
        else
            sum -= cur;
    &#125;
    return r - sum;
&#125;
</code></pre>
<p>算法的复杂度为 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>。</p>
<h4 id="求在给定区间内，能被给定集合至少一个数整除的数个数"><a href="#求在给定区间内，能被给定集合至少一个数整除的数个数" class="headerlink" title="求在给定区间内，能被给定集合至少一个数整除的数个数"></a>求在给定区间内，能被给定集合至少一个数整除的数个数</h4><p>给出 n 个整数 ai 和整数 r。求在区间[1;r]中，至少能被一个 ai 整除的数有多少。</p>
<p>解决此题的思路和上题差不多，计算 ai 所能组成的各种集合（这里将集合中 ai 的最小公倍数作为除数）在区间中满足的数的个数，然后利用容斥原理实现加减。</p>
<p>此题中实现所有集合的枚举，需要 2^n 的复杂度，求解 lcm 需要 O(nlogr)的复杂度。</p>
<h4 id="能满足一定数目匹配的字符串的个数问题"><a href="#能满足一定数目匹配的字符串的个数问题" class="headerlink" title="能满足一定数目匹配的字符串的个数问题"></a>能满足一定数目匹配的字符串的个数问题</h4><p>给出 n 个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数 k，求能正好匹配 k 个匹配串的字符串的个数。更进一步，求至少匹配 k 个匹配串的字符串的个数。</p>
<p>首先我们会发现，我们很容易找到能匹配所有匹配串的字符串。只需要对比所有匹配串，去在每一列中找出现的字母（或者这一列全是’?’，或者这一列出现了唯一的字母，否则这样的字符串就存在），最后所有字母组成的单词即为所求。</p>
<p>现在我们来学习如何解决<strong>第一个问题</strong>：能正好匹配 k 个匹配串的字符串。</p>
<p>我们在 n 个匹配串中选出 k 个，作为集合 X，统计满足集合 X 中匹配的字符串数。求解这个问题时应用容斥原理，对 X 的所有超集进行运算，得到每个 X 集合的结果：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjg1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>此处 f(Y)代表满足匹配集合 Y 的字符串数。</p>
<p>如果我们将所有的 ans(X)相加，就可以得到最终结果：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMjkucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>这样，就得到了一个复杂度<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的解法。</p>
<p>这个算法可以作一些改进，因为在求解 ans(X)时有些 Y 集合是重复的。</p>
<p>回到利用容斥原理公式可以发现，当选定一个 Y 时，所有 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>中 X 的结果都是相同的，其符号都为<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>。所以可以用如下公式求解：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>这样就得到了一个复杂度<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzM1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的解法。</p>
<p>现在我们来求解<strong>第二个问题</strong>：能满足<strong>至少</strong>k 个匹配的字符串有多少个。</p>
<p>显然的，我们可以用问题一的方法来计算满足 k 到 n 的所有结果。问题一的结论依然成立，不同之处在于这个问题中的 X 不是大小都为 k 的，而是&gt;&#x3D;k 的所有集合。</p>
<p>如此进行计算，最后将 f(Y)作为另一个因子：将所有的 ans 做和，有点类似二项式展开：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>在《具体数学》( <a target="_blank" rel="noopener" href="http://e-maxx.ru/bookz/files/graham.djvu">Graham, Knuth, Patashnik. <strong>“Concrete Mathematics”</strong> [1998]</a> )中，介绍了一个著名的关于二项式系数的公式：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzUucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>根据这个公式，可以将前面的结果进行化简：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>那么，对于这个问题，我们也得到了一个<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的解法：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzgucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<h4 id="路径的数目问题"><a href="#路径的数目问题" class="headerlink" title="路径的数目问题"></a>路径的数目问题</h4><p>在一个的<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzg1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>方格阵中，有 k 个格子是不可穿越的墙。一开始在格子(1,1)（最左下角的格子）中有一个机器人。这个机器人只能向上或向右行进，最后它将到达位于格子(n,m)的笼子里，其间不能经过障碍物格子。求一共有多少种路线可以到达终点。</p>
<p>为了方便区分所有障碍物格子，我们建立坐标系，用(x,y)表示格子的坐标。</p>
<p>首先我们考虑没有障碍物的时候：也就是如何求从一个点到另一个点的路径数。如果从一个点在一个方向要走 x 个格子，在另一个方向要走 y 个格子，那么通过简单的组合原理可以得知结果为：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wMzkucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>现在来考虑有障碍物时的情况，我们可以利用容斥原理：求出至少经过一个障碍物时的路径数。</p>
<p>对于这个例子，你可以枚举所有障碍物的子集，作为需要要经过的，计算经过该集合障碍物的路径数（求从原点到第一个障碍物的路径数、第一个障碍物到第二个障碍物的路径数…最后对这些路径数求乘积），然后通过容斥原理，对这些结果作加法或减法。</p>
<p>然而，它是一个<strong>非多项式的解法</strong>，复杂度<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>。下面我们将介绍一个<strong>多项式的解法</strong>。</p>
<p>我们运用<strong>动态规划</strong>：令 d[i][j]代表从第 i 个点到第 j 个点，不经过任何障碍物时的路径数（当然除了 i 和 j）。那么我们总共需要 k+2 个点，包括 k 个障碍物点以及起点和终点。</p>
<p>首先我们算出从 i 点到 j 点的所有路径数，然后减掉经过障碍物的那些“坏”的路线。让我们看看如何计算“坏”的路线：枚举 i 和 j 之间的所有障碍物点 i&lt;l&lt;j，那么从 i 到 j 的“坏”路径数就是所有 d[i][l]和 d[l][j]的乘积最后求和。再被总路径数减掉就是 d[i][j]的结果。</p>
<p>我们已经知道计算总路径数的复杂度为 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，那么该解法的总复杂度为 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>。</p>
<p><em>（译注：当然也有 O(nm)的 dp 解法，根据 n、m、k 的值可以采取适当的解法）</em></p>
<h4 id="素数四元组的个数问题"><a href="#素数四元组的个数问题" class="headerlink" title="素数四元组的个数问题"></a>素数四元组的个数问题</h4><p>给出 n 个数<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDI1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，从其中选出 4 个数，使它们的最大公约数为 1，问总共有多少中取法。</p>
<p>我们解决它的逆问题：求最大公约数 d&gt;1 的四元组的个数。</p>
<p>运用容斥原理，将求得的对于每个 d 的四元组个数的结果进行加减。</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>其中 deg(d)代表 d 的质因子个数，f(d)代表四个数都能被 d 整除的四元组的个数。</p>
<p>求解 f(d)时，只需要利用组合方法，求从所有满足被 d 整除的 ai 中选 4 个的方法数。</p>
<p>然后利用容斥原理，统计出所有能被一个素数整除的四元组个数，然后减掉所有能被两个素数整除的四元组个数，再加上被三个素数整除的四元组个数…</p>
<h4 id="和睦数三元组的个数问题"><a href="#和睦数三元组的个数问题" class="headerlink" title="和睦数三元组的个数问题"></a>和睦数三元组的个数问题</h4><p>给出一个整数<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDM1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload> 。选出 a, b, c (其中 2&lt;&#x3D;a&lt;b&lt;c&lt;&#x3D;n)，组成<strong>和睦三元组</strong>，即：</p>
<p>· 或者满足 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>， <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDUucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload> ， <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>·或者满足<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>首先，我们考虑它的逆问题：也就是<strong>不和睦三元组</strong>的个数。</p>
<p>然后，我们可以发现，在每个<strong>不和睦三元组</strong>的三个元素中，我们都能找到正好两个元素满足：它与一个元素互素，并且与另一个元素不互素。</p>
<p>所以，我们只需枚举 2 到 n 的所有数，将每个数的与其互素的数的个数和与其不互素的数的个数相乘，最后求和并除以 2，就是要求的逆问题的答案。</p>
<p>现在我们要考虑这个问题，如何求与 2 到 n 这些数互素（不互素）的数的个数。虽然求解与一个数互素数的个数的解法在前面已经提到过了，但在此并不合适，因为现在要求 2 到 n 所有数的结果，分别求解显然效率太低。</p>
<p>所以，我们需要一个更快的算法，可以一次算出 2 到 n 所有数的结果。</p>
<p>在这里，我们可以使用<strong>改进的埃拉托色尼筛法</strong>。</p>
<p>·首先，对于 2 到 n 的所有数，我们要知道构成它的素数中是否有次数大于 1 的，为了应用容斥原理，我们还有知道它们由多少种不同的素数构成。</p>
<p>对于这个问题，我们定义数组 deg[i]：表示 i 由多少种不同素数构成，以及 good[i]：取值 true 或 false，表示 i 包含素数的<strong>次数小于等于 1</strong>是否成立。</p>
<p>再利用埃拉托色尼筛法，在遍历到某个素数 i 时，枚举它在 2 到 n 范围内的所有倍数，更新这些倍数的 deg[]值，如果有倍数包含了多个 i，那么就把这个倍数的 good[]值赋为 false。</p>
<p>·然后，利用容斥原理，求出 2 到 n 每个数的 cnt[i]：在 2 到 n 中不与 i 互素的数的个数。</p>
<p>回想容斥原理的公式，它所求的集合是不会包含重复元素的。也就是如果这个集合包含的某个素数多于一次，它们不应再被考虑。</p>
<p>所以只有当一个数 i 满足 good[i]&#x3D;true 时，它才会被用于容斥原理。枚举 i 的所有倍数 i<em>j，那么对于 i</em>j，就有 N&#x2F;i 个与 i*j 同样包含 i（素数集合）的数。将这些结果进行加减，符号由 deg[i]（素数集合的大小）决定。如果 deg[i]为奇数，那么我们要用加号，否则用减号。</p>
<p><strong>程序实现：</strong></p>
<pre><code class="hljs"> 
</code></pre>
<ol>
<li><pre><code class="hljs"> int n;
</code></pre>
<p> bool good[MAXN];</p>
<p> int deg[MAXN], cnt[MAXN];</p>
<p> long long solve() {</p>
<pre><code class="hljs">      memset (good, 1, sizeof good);

      memset (deg, 0, sizeof deg);

      memset (cnt, 0, sizeof cnt);



      long long ans_bad = 0;

      for (int i=2; i&lt;=n; ++i) &#123;

              if (good[i]) &#123;

                       if (deg[i] == 0) deg[i] = 1;

                       for (int j=1; i*j&lt;=n; ++j) &#123;

                                if (j &gt; 1 &amp;&amp; deg[i] == 1)

                                         if (j % i == 0)

                                                 good[i*j] = false;

                                         else

                                                 ++deg[i*j];

                                cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);

                       &#125;

              &#125;

              ans_bad += (cnt[i] - 1) * 1ll * (n - cnt[i] - 1);

      &#125;

      return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
</code></pre>
<p> }</p>
</li>
</ol>
<p>最终算法的复杂度为 <img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDgucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，因为对于大部分 i 都要进行 n&#x2F;i 次枚举。</p>
<h4 id="错排问题"><a href="#错排问题" class="headerlink" title="错排问题"></a>错排问题</h4><p>我们想要证明如下的求解长度为 n 序列的错排数的公式：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNDkucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>它的近似结果为：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTAucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>（此外，如果将这个近似式的结果向其最近的整数舍入，你就可以得到准确结果）</p>
<p>我们定义 Ak：在长度为 n 的序列中，有一个不动点位置为 k(1&lt;&#x3D;k&lt;&#x3D;n)时的序列集合。</p>
<p>现在我们运用容斥原理来计算至少包含有一个不动点的排列数，要计算这个，我们必须先算出所有 Ak、以及它们的交集的排列数。</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTEucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload><br><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTIucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload><br><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTMucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload><br>因为我们知道当有 x 个不动点时，所有不动点的位置是固定的，而其它点可以任意排列。</p>
<p>用容斥原理对结果进行带入，而从 n 个点中选 x 个不动点的组合数为<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTM1LnBuZw?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>，那么至少包含一个不动点的排列数为：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTQucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>那么不包含不动点（即错排数）的结果就是：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTUucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>化简这个式子，我们得到了错排数的准确式和近似式：</p>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTYucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload></p>
<p>（因为括号中是<img src="https://imgconvert.csdnimg.cn/aHR0cDovL3d3dy5jcHBibG9nLmNvbS9pbWFnZXMvY3BwYmxvZ19jb20vdmljaS8wNTcucG5n?x-oss-process=image/format,png" srcset="/img/loading.gif" lazyload>的泰勒展开式的前 n+1 项）</p>
<p>用这个式子也可以解决一些类似的问题，如果现在求有 m 个不动点的排列数，那么我们可以对上式进行修改，也就是将括号中的累加到 1&#x2F;n!改成累加到 1&#x2F;(n-m)!。</p>
<h3 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h3><p>求 1 到 n 范围内能被 5，6，8 整除的数的个数。（0&lt;n&lt;10^7）输入</p>
<p>多组数据，处理到文件结尾。</p>
<p>每行输入一个 n；</p>
<h3 id="输出"><a href="#输出" class="headerlink" title="输出"></a>输出</h3><p>输出结果，每个结果占一行。</p>
<h3 id="示例输入"><a href="#示例输入" class="headerlink" title="示例输入"></a>示例输入</h3><pre><code class="hljs">1000
</code></pre>
<h3 id="示例输出"><a href="#示例输出" class="headerlink" title="示例输出"></a>示例输出</h3><pre><code class="hljs">400



    #include &lt;iostream&gt;
    #include&lt;cstdio&gt;
    #include&lt;cstring&gt;
    #include&lt;algorithm&gt;
    using namespace std;
    int main()
    &#123;
        int i,j,k,n,b,a;
        while(cin&gt;&gt;n)
        &#123;
            b = n/30+n/24+n/40;
        a = n/120;
        k = n/5+n/6+n/8;
        cout&lt;&lt;k-b+a&lt;&lt;endl;
        &#125;

        return 0;
    &#125;
</code></pre>
<h3 id="在-OJ-的相关题目"><a href="#在-OJ-的相关题目" class="headerlink" title="在 OJ 的相关题目"></a>在 OJ 的相关题目</h3><p>这里列出了一些可以用容斥原理解决的习题。<br><a target="_blank" rel="noopener" href="http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1266">· UVA #10325 <strong>“The Lottery”</strong> [难度：简单]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2906">UVA #11806 <strong>“Cheerleaders”</strong> [难度：简单]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.topcoder.com/stat?c=problem_statement&pm=10875">TopCoder SRM 477 <strong>“CarelessSecretary”</strong> [难度：简单]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://community.topcoder.com/stat?c=problem_statement&pm=6658&rd=10068">TopCoder TCHS 16 <strong>“Divisibility”</strong> [难度：简单]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.spoj.pl/problems/NGM2/">SPOJ #6285 NGM2 <strong>“Another Game With Numbers”</strong> [难度：简单]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://community.topcoder.com/stat?c=problem_statement&pm=8470">TopCoder SRM 382 <strong>“CharmingTicketsEasy”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.topcoder.com/stat?c=problem_statement&pm=8307">TopCoder SRM 390 <strong>“SetOfPatterns”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://community.topcoder.com/stat?c=problem_statement&pm=2013">TopCoder SRM 176 <strong>“Deranged”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://community.topcoder.com/stat?c=problem_statement&pm=10702&rd=14144&rm=303184&cr=22697599">TopCoder SRM 457 <strong>“TheHexagonsDivOne”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.spoj.pl/problems/MSKYCODE/">SPOJ #4191 MSKYCODE <strong>“Sky Code”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.spoj.pl/problems/SQFREE/">SPOJ #4168 SQFREE <strong>“Square-free integers”</strong> [难度：中等]</a></p>
<p>· <a target="_blank" rel="noopener" href="http://www.codechef.com/JAN11/problems/COUNTREL/">CodeChef <strong>“Count Relations”</strong> [难度：中等]</a></p>
<h3 id="参考文献"><a href="#参考文献" class="headerlink" title="参考文献"></a>参考文献</h3><p>Debra K. Borkovitz. <strong><a target="_blank" rel="noopener" href="http://faculty.wheelock.edu/dborkovitz/articles/ngm6.htm">“Derangements and the Inclusion-Exclusion Principle”</a></strong></p>
<p><strong>原文链接：</strong><a target="_blank" rel="noopener" href="https://blog.csdn.net/m0_37286282/article/details/78869512">https://blog.csdn.net/m0_37286282/article/details/78869512</a></p>

                
              </div>
            
            <hr/>
            <div>
              <div class="post-metas my-3">
  
    <div class="post-meta mr-3 d-flex align-items-center">
      <i class="iconfont icon-category"></i>
      

<span class="category-chains">
  
  
    
      <span class="category-chain">
        
  <a href="/categories/%E7%AE%97%E6%B3%95/" class="category-chain-item">算法</a>
  
  
    <span>></span>
    
  <a href="/categories/%E7%AE%97%E6%B3%95/ACM%E7%AB%9E%E8%B5%9B/" class="category-chain-item">ACM竞赛</a>
  
  
    <span>></span>
    
  <a href="/categories/%E7%AE%97%E6%B3%95/ACM%E7%AB%9E%E8%B5%9B/%E6%95%B0%E5%AD%A6/" class="category-chain-item">数学</a>
  
  
    <span>></span>
    
  <a href="/categories/%E7%AE%97%E6%B3%95/ACM%E7%AB%9E%E8%B5%9B/%E6%95%B0%E5%AD%A6/%E6%95%B0%E8%AE%BA/" class="category-chain-item">数论</a>
  
  

  

  

  

      </span>
    
  
</span>

    </div>
  
  
</div>


              
  

  <div class="license-box my-3">
    <div class="license-title">
      <div>『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）</div>
      <div>http://example.com/2023/12/06/『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）/</div>
    </div>
    <div class="license-meta">
      
        <div class="license-meta-item">
          <div>作者</div>
          <div>Chiam</div>
        </div>
      
      
        <div class="license-meta-item license-meta-date">
          <div>发布于</div>
          <div>2023年12月6日</div>
        </div>
      
      
      
        <div class="license-meta-item">
          <div>许可协议</div>
          <div>
            
              
              
                <a class="print-no-link" target="_blank" href="https://creativecommons.org/licenses/by/4.0/">
                  <span class="hint--top hint--rounded" aria-label="BY - 署名">
                    <i class="iconfont icon-by"></i>
                  </span>
                </a>
              
            
          </div>
        </div>
      
    </div>
    <div class="license-icon iconfont"></div>
  </div>



              
                <div class="post-prevnext my-3">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E6%95%B0%E5%AD%A6-%E6%95%B0%E8%AE%BA%E3%80%8F%E5%B9%BF%E4%B9%89%E6%AC%A7%E6%8B%89%E9%99%8D%E5%B9%82%EF%BC%88%E6%A8%A1%E6%9D%BF%EF%BC%89/" title="『算法-ACM竞赛-数学-数论』广义欧拉降幂（模板）">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">『算法-ACM竞赛-数学-数论』广义欧拉降幂（模板）</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E6%95%B0%E5%AD%A6-%E6%95%B0%E8%AE%BA%E3%80%8F%E5%9B%A0%E5%AD%90%E5%92%8C%E7%BA%BF%E6%80%A7%E7%AD%9B%20%EF%BC%88%E6%A8%A1%E6%9D%BF)/" title="『算法-ACM竞赛-数学-数论』因子和线性筛 （模板)">
                        <span class="hidden-mobile">『算法-ACM竞赛-数学-数论』因子和线性筛 （模板)</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
  
  
    <article id="comments" lazyload>
      
  <div id="valine"></div>
  <script type="text/javascript">
    Fluid.utils.loadComments('#valine', function() {
      Fluid.utils.createScript('https://lib.baomitu.com/valine/1.5.1/Valine.min.js', function() {
        var options = Object.assign(
          {"appId":"fIfc7WqUDZohlQuPc2lz5mJy-MdYXbMMI","appKey":"zjlAG3ZA3o4cBHVAkjzc2Z20","path":"window.location.pathname","placeholder":"留言仅限讨论，禁止广告等行为","avatar":"retro","meta":["nick","mail","link"],"requiredFields":[],"pageSize":10,"lang":"zh-CN","highlight":false,"recordIP":false,"serverURLs":"https://fifc7wqu.api.lncldglobal.com","emojiCDN":null,"emojiMaps":null,"enableQQ":false},
          {
            el: "#valine",
            path: window.location.pathname
          }
        )
        new Valine(options);
        Fluid.utils.waitElementVisible('#valine .vcontent', () => {
          var imgSelector = '#valine .vcontent img:not(.vemoji)';
          Fluid.plugins.imageCaption(imgSelector);
          Fluid.plugins.fancyBox(imgSelector);
        })
      });
    });
  </script>
  <noscript>Please enable JavaScript to view the comments</noscript>


    </article>
  


          </article>
        </div>
      </div>
    </div>

    <div class="side-col d-none d-lg-block col-lg-2">
      
  <aside class="sidebar" style="margin-left: -1rem">
    <div id="toc">
  <p class="toc-header">
    <i class="iconfont icon-list"></i>
    <span>目录</span>
  </p>
  <div class="toc-body" id="toc-body"></div>
</div>



  </aside>


    </div>
  </div>
</div>





  



  



  



  



  







    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v" for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>

    

    
  </main>

  <footer>
    <div class="footer-inner">
  
    <div class="footer-content">
       <meta name="referrer" content="no-referrer" /> <footer id="footer" role="contentinfo"> <div class="divider"> <div class="wall"></div> <img class="animals" src="/img/footer_animals_new.png" srcset="/img/loading.gif" lazyload alt="Footer Animals"> </div> <div class="container" data-index="450"> <p> <a href="https://chiamzhang.github.io" target="_blank">DogEgg</a> <i class="iconfont icon-love"></i> <a href="#" target="_blank">LittePig</a> </p> <p> Powered by  <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-pen"></i> Theme  <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a> </p> </div> </footer> 
    </div>
  
  
  
  
</div>

  </footer>

  <!-- Scripts -->
  
  <script  src="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://lib.baomitu.com/jquery/3.6.4/jquery.min.js" ></script>
<script  src="https://lib.baomitu.com/twitter-bootstrap/4.6.1/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>


  <script  src="https://lib.baomitu.com/typed.js/2.0.12/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var subtitle = document.getElementById('subtitle');
      if (!subtitle || !typing) {
        return;
      }
      var text = subtitle.getAttribute('data-typed-text');
      
        typing(text);
      
    })(window, document);
  </script>




  
    <script  src="/js/img-lazyload.js" ></script>
  




  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/tocbot/4.20.1/tocbot.min.js', function() {
    var toc = jQuery('#toc');
    if (toc.length === 0 || !window.tocbot) { return; }
    var boardCtn = jQuery('#board-ctn');
    var boardTop = boardCtn.offset().top;

    window.tocbot.init(Object.assign({
      tocSelector     : '#toc-body',
      contentSelector : '.markdown-body',
      linkClass       : 'tocbot-link',
      activeLinkClass : 'tocbot-active-link',
      listClass       : 'tocbot-list',
      isCollapsedClass: 'tocbot-is-collapsed',
      collapsibleClass: 'tocbot-is-collapsible',
      scrollSmooth    : true,
      includeTitleTags: true,
      headingsOffset  : -boardTop,
    }, CONFIG.toc));
    if (toc.find('.toc-list-item').length > 0) {
      toc.css('visibility', 'visible');
    }

    Fluid.events.registerRefreshCallback(function() {
      if ('tocbot' in window) {
        tocbot.refresh();
        var toc = jQuery('#toc');
        if (toc.length === 0 || !tocbot) {
          return;
        }
        if (toc.find('.toc-list-item').length > 0) {
          toc.css('visibility', 'visible');
        }
      }
    });
  });
</script>


  <script src=https://lib.baomitu.com/clipboard.js/2.0.11/clipboard.min.js></script>

  <script>Fluid.plugins.codeWidget();</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/anchor-js/4.3.1/anchor.min.js', function() {
    window.anchors.options = {
      placement: CONFIG.anchorjs.placement,
      visible  : CONFIG.anchorjs.visible
    };
    if (CONFIG.anchorjs.icon) {
      window.anchors.options.icon = CONFIG.anchorjs.icon;
    }
    var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
    var res = [];
    for (var item of el) {
      res.push('.markdown-body > ' + item.trim());
    }
    if (CONFIG.anchorjs.placement === 'left') {
      window.anchors.options.class = 'anchorjs-link-left';
    }
    window.anchors.add(res.join(', '));

    Fluid.events.registerRefreshCallback(function() {
      if ('anchors' in window) {
        anchors.removeAll();
        var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
        var res = [];
        for (var item of el) {
          res.push('.markdown-body > ' + item.trim());
        }
        if (CONFIG.anchorjs.placement === 'left') {
          anchors.options.class = 'anchorjs-link-left';
        }
        anchors.add(res.join(', '));
      }
    });
  });
</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.js', function() {
    Fluid.plugins.fancyBox();
  });
</script>


  <script>Fluid.plugins.imageCaption();</script>

  <script  src="/js/local-search.js" ></script>




  
<script src="/js/love.js"></script>
<script src="/js/funnyTitle.js"></script>
<script src="/js/backTop.js"></script>
<script src="//cdn.jsdelivr.net/gh/bynotes/texiao/source/js/xiaoxuehua.js"></script>



<!-- 主题的启动项，将它保持在最底部 -->
<!-- the boot of the theme, keep it at the bottom -->
<script  src="/js/boot.js" ></script>


  

  <noscript>
    <div class="noscript-warning">博客在允许 JavaScript 运行的环境下浏览效果更佳</div>
  </noscript>
<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/wanko.model.json"},"display":{"position":"left","width":150,"height":150,"hOffset":20,"vOffset":0},"mobile":{"show":false,"scale":0.5},"react":{"opacity":0.9},"log":false});</script></body>
</html>
